﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace project_math
{
    class CalTools
    {
        //获取最大公约数
        public static int get_Yue(int num1, int num2)
        {
            int tmp;
            if (num1 < num2)
            {
                tmp = num1; num1 = num2; num2 = tmp;
            }
            int a = num1; int b = num2;
            while (b != 0)
            {
                tmp = a % b;
                a = b;
                b = tmp;
            }
            return a;
        }
        //获取最小公倍数
        public static int get_Bei(int num1, int num2)
        {
            int y = CalTools.get_Yue(num1, num2);
            return num1 * num2 / y;
        }
        //计算一个运算符节点
        public static Number calcute_number(Number num1, Number num2, string op)
        {
            if (op.Equals("+") || op.Equals("-"))
            {
                int num1_tr = 1, num2_tr = 1;
                int new_deno = num1.getdenominator();
                if (num1.getdenominator() != num2.getdenominator())//分母不一样，通分
                {
                    new_deno = CalTools.get_Bei(num1.getdenominator(), num2.getdenominator());
                    num1_tr = (new_deno / num1.getdenominator());
                    num2_tr = (new_deno / num2.getdenominator());
                }
                int new_num1 = num1_tr * num1.getnumerator();
                int new_num2 = num2_tr * num2.getnumerator();
                int new_num = 0;
                if (op.Equals("+")) new_num = new_num1 + new_num2;
                else new_num = new_num1 - new_num2;
                Number result_num = new Number(new_num, new_deno);
                result_num.adjust();
                return result_num;
            }
            else
            {
                int new_deno = 0, new_num = 0;
                if (op.Equals("*"))
                {
                    new_deno = num1.getdenominator() * num2.getdenominator();
                    new_num = num1.getnumerator() * num2.getnumerator();
                }
                else
                {
                    new_deno = num1.getdenominator() * num2.getnumerator();
                    new_num = num1.getnumerator() * num2.getdenominator();
                }
                Number result_num = new Number(new_num, new_deno);
                result_num.adjust();
                return result_num;
            }
        }
        //比较两个运算符的优先级
        public static int test_op(string a, string b)
        {
            if (a.Equals("+") || a.Equals("-"))
            {
                if (b.Equals("*") || b.Equals("/"))
                {
                    return 0;
                }
                else
                {
                    return 1;
                }
            }
            else return 1;
        }
    }

    //数据统一表示为分数 
    class Number
    {
        private int numerator;
        private int denominator;
        private float value;
        public Number(int numerator, int denominator)
        {
            this.numerator = numerator;
            this.denominator = denominator;
            this.value = (float)numerator / (float)denominator;
        }
        public void setnumerator(int n){
            this.numerator = n;
        }
        public void setdenominator(int n)
        {
            this.denominator = n;
        }
        public int getnumerator()
        {
            return this.numerator;
        }
        public int getdenominator()
        {
            return this.denominator;
        }
        public float getvalue()
        {
            return this.value;
        }
        public string ToString()
        {
            string s = "";
            string tag = "";
            if (this.numerator * this.denominator < 0)
            {
                tag = "-";
            }
            if (this.numerator % this.denominator != 0)
            {
                int prior = Math.Abs(this.numerator) / Math.Abs(this.denominator);
                int post = Math.Abs(this.numerator) % Math.Abs(this.denominator);
                if (prior > 0)
                {
                    s = "(" +tag+ prior.ToString() + "'" + post.ToString() + "/" + Math.Abs(this.denominator).ToString() + ")";
                }
                else
                {
                    s = "(" +tag+ Math.Abs(this.numerator).ToString() + "/" + Math.Abs(this.denominator).ToString() + ")";
                }
            }
            else
            {
                s = tag+(Math.Abs(this.numerator) / Math.Abs(this.denominator)).ToString();
            }
            //s = "(" + this.numerator.ToString() + "/" + this.denominator.ToString() + ")";
            return s;
        }
        public void adjust()
        {
            int yue = CalTools.get_Yue(this.numerator, this.denominator);
            if (yue != 1)
            {
                this.numerator = this.numerator / yue;
                this.denominator = this.denominator / yue;
            }
        }
    }
    //节点
    class TreeNode
    {
        public int type;
        public string op;
        public string s;
        public Number value;
        public TreeNode left;
        public TreeNode right;
    }
    //值节点
    class NumNode : TreeNode
    {
        public NumNode(Number value)
        {
            this.type = 1;
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }
    //运算符节点
    class OpNode : TreeNode
    {
        public OpNode(string op)
        {
            this.type = 2;
            this.op = op;
            this.value = null;
            this.left = null;
            this.right = null;
        }
        public void calcute()
        {
            this.value = CalTools.calcute_number(this.left.left.value, this.right.right.value, this.op);
        }
    }
    //二叉树定义
    class BinaryTree
    {
        TreeNode root;//根节点
        int height;//高度
        int number;//长度即包含的运算符数量
        public TreeNode getroot(){
            return root;
        }
        public int getheight()
        {
            return height;
        }
        public int getnumber()
        {
            return number;
        }
        public BinaryTree(TreeNode root, int number)
        {
            this.root = root;
            this.height = 0;
            this.number = number;
        }
        //调整为左子树永远比右子树大
        public void adjustTree(TreeNode root)
        {
            if (root.left != null)
            {
                adjustTree(root.left);
            }
            if (root.right != null)
            {
                adjustTree(root.right);
            }
            if (root.left != null && root.right != null)
            {
                if (root.left.value.getvalue() < root.right.value.getvalue())
                {
                    TreeNode tmp = root.right;
                    root.right = root.left;
                    root.left = tmp;
                }
            }
        }
        //后序遍历表达式，并生成其字符串
        public Number OrderTra(TreeNode root,TreeNode last)
        {
            if (root != null)
            {
                if (root.type == 1)
                {
                    root.s = root.value.ToString();
                    return root.value;
                }
                else
                {
                    Number left = OrderTra(root.left, root);
                    Number right = OrderTra(root.right, root);
                    root.s = root.left.s + root.op + root.right.s;
                    if (CalTools.test_op(root.op, last.op) == 0)
                    {
                        root.s = "(" + root.s + ")";
                    }
                    root.value = CalTools.calcute_number(left, right, root.op);
                    last = root;
                    return root.value;
                }
            }
            return null;
        }
    }

    class Items
    {
        Random rd = new Random();
        //生成随机数
        public NumNode createNum(int span)
        {
            int num1 = (int)rd.Next(1, span + 1);
            int num2 = (int)rd.Next(1, span + 1);
            return new NumNode(new Number(num1, num2));
        }
        //随机计算符
        public OpNode createOperator(TreeNode left,TreeNode right)
        {
            string s = "+";
            int ran = rd.Next(1, 5);
            switch (ran)
            {
                case 1:
                    s = "+";
                    break;
                case 2:
                    s = "-";
                    break;
                case 3:
                    s = "*";
                    break;
                case 4:
                    s = "/";
                    break;
            }
            OpNode opnode = new OpNode(s);
            opnode.left = left;
            opnode.right = right;
            return opnode;
        }
        //创建表达式
        public BinaryTree createQues(int span,int max_len)
        {
            TreeNode left, right;
            NumNode num_1 = this.createNum(span);
            left = num_1;
            for (int i = 0; i < max_len-1; i++)
            {
                NumNode num_2 = this.createNum(span);
                right = num_2;
                OpNode op = this.createOperator(left, right);
                left = op;
            }
            BinaryTree tree = new BinaryTree(left, max_len);
            tree.OrderTra(tree.getroot(),tree.getroot());
            return tree;
        }
        //创建多个表达式,用list存储
        public List<BinaryTree> createQList(int totle, int span,int max_len)
        {
            List<BinaryTree> temp = new List<BinaryTree>();
            BinaryTree s = null;
            for (int i = 0; i < totle; i++)
            {
                int m_len = rd.Next(2, max_len + 1);
                s = this.createQues(span, m_len);
                s.adjustTree(s.getroot());
                temp.Add(s);
            }
            return temp;
        }
        //比较树结构查重
        public int compareTree(BinaryTree tree1,BinaryTree tree2){
            if(tree1.getheight() != 　tree1.getheight())
            {
                return 1;
            }
            //1.树的高度不同
            if (tree1.getnumber() != tree1.getnumber())
            {
                return 1;
            }

            //2.树的结构不同
            if(compareNode(tree1.getroot(),tree2.getroot())==1){
                return 1;
            }
            return 0;
        }
        public int compareNode(TreeNode node1, TreeNode node2)
        {
            //比较节点的类型
            if (node1.type != node2.type)
            {
                return 1;
            }
            else
            {
                int l=0, r=0;
                if (node1.left != null && node2.left != null)
                {
                    l=compareNode(node1.left, node2.left);
                }
                if (node1.right != null && node2.right != null)
                {
                    r = compareNode(node1.right, node2.right);
                }
                if (l == 0 && r == 0 && node1.value.getnumerator() == node2.value.getnumerator()&& node1.value.getdenominator() == node2.value.getdenominator())
                {
                    return 0;
                }
                return 1;
            }
        }
    }
}
